A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition
Identifieur interne : 000012 ( LNCS/Analysis ); précédent : 000011; suivant : 000013A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition
Auteurs : Binh-Minh Bui-Xuan [Norvège] ; Pinar Heggernes [Norvège] ; Daniel Meister [Allemagne] ; Andrzej Proskurowski [États-Unis]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2011.
Abstract
Abstract: A set family is a collection of sets over a universe. If a set family satisfies certain closure properties then it admits an efficient representation of its members by labeled trees. The size of the tree is proportional to the size of the universe, whereas the number of set family members can be exponential. Computing such efficient representations is an important task in algorithm design. Set families are usually not given explicitly (by listing their members) but represented implicitly. We consider the problem of efficiently computing tree representations of set families. Assuming the existence of efficient algorithms for solving the Membership and Separation problems, we prove that if a set family satisfies weak closure properties then there exists an efficient algorithm for computing a tree representation of the set family. The running time of the algorithm will mainly depend on the running times of the algorithms for the two basic problems. Our algorithm generalizes several previous results and provides a unified approach to the computation for a large class of decompositions of graphs. We also introduce a decomposition notion for directed graphs which has no undirected analogue. We show that the results of the first part of the paper are applicable to this new decomposition. Finally, we give efficient algorithms for the two basic problems and obtain an ${\cal O}(n^3)$ -time algorithm for computing a tree representation.
Url:
DOI: 10.1007/978-3-642-22685-4_30
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001B88
- to stream Istex, to step Curation: 001A71
- to stream Istex, to step Checkpoint: 000234
- to stream Main, to step Merge: 000A52
- to stream Main, to step Curation: 000A21
- to stream Main, to step Exploration: 000A21
- to stream LNCS, to step Extraction: 000012
Links to Exploration step
ISTEX:E0D5AC59000A21FA35884564DF9E64538F6ECD66Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition</title><author><name sortKey="Bui Xuan, Binh Minh" sort="Bui Xuan, Binh Minh" uniqKey="Bui Xuan B" first="Binh-Minh" last="Bui-Xuan">Binh-Minh Bui-Xuan</name></author><author><name sortKey="Heggernes, Pinar" sort="Heggernes, Pinar" uniqKey="Heggernes P" first="Pinar" last="Heggernes">Pinar Heggernes</name></author><author><name sortKey="Meister, Daniel" sort="Meister, Daniel" uniqKey="Meister D" first="Daniel" last="Meister">Daniel Meister</name></author><author><name sortKey="Proskurowski, Andrzej" sort="Proskurowski, Andrzej" uniqKey="Proskurowski A" first="Andrzej" last="Proskurowski">Andrzej Proskurowski</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:E0D5AC59000A21FA35884564DF9E64538F6ECD66</idno><date when="2011" year="2011">2011</date><idno type="doi">10.1007/978-3-642-22685-4_30</idno><idno type="url">https://api.istex.fr/document/E0D5AC59000A21FA35884564DF9E64538F6ECD66/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001B88</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001B88</idno><idno type="wicri:Area/Istex/Curation">001A71</idno><idno type="wicri:Area/Istex/Checkpoint">000234</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000234</idno><idno type="wicri:doubleKey">0302-9743:2011:Bui Xuan B:a:generic:approach</idno><idno type="wicri:Area/Main/Merge">000A52</idno><idno type="wicri:Area/Main/Curation">000A21</idno><idno type="wicri:Area/Main/Exploration">000A21</idno><idno type="wicri:Area/LNCS/Extraction">000012</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition</title><author><name sortKey="Bui Xuan, Binh Minh" sort="Bui Xuan, Binh Minh" uniqKey="Bui Xuan B" first="Binh-Minh" last="Bui-Xuan">Binh-Minh Bui-Xuan</name><affiliation wicri:level="1"><country xml:lang="fr">Norvège</country><wicri:regionArea>Department of Informatics, University of Bergen</wicri:regionArea><wicri:noRegion>University of Bergen</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Norvège</country></affiliation></author><author><name sortKey="Heggernes, Pinar" sort="Heggernes, Pinar" uniqKey="Heggernes P" first="Pinar" last="Heggernes">Pinar Heggernes</name><affiliation wicri:level="1"><country xml:lang="fr">Norvège</country><wicri:regionArea>Department of Informatics, University of Bergen</wicri:regionArea><wicri:noRegion>University of Bergen</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Norvège</country></affiliation></author><author><name sortKey="Meister, Daniel" sort="Meister, Daniel" uniqKey="Meister D" first="Daniel" last="Meister">Daniel Meister</name><affiliation wicri:level="4"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Theoretical Computer Science, University of Trier</wicri:regionArea><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Proskurowski, Andrzej" sort="Proskurowski, Andrzej" uniqKey="Proskurowski A" first="Andrzej" last="Proskurowski">Andrzej Proskurowski</name><affiliation wicri:level="1"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Information and Computer Science, University of Oregon</wicri:regionArea><wicri:noRegion>University of Oregon</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2011</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">E0D5AC59000A21FA35884564DF9E64538F6ECD66</idno><idno type="DOI">10.1007/978-3-642-22685-4_30</idno><idno type="ChapterID">30</idno><idno type="ChapterID">Chap30</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: A set family is a collection of sets over a universe. If a set family satisfies certain closure properties then it admits an efficient representation of its members by labeled trees. The size of the tree is proportional to the size of the universe, whereas the number of set family members can be exponential. Computing such efficient representations is an important task in algorithm design. Set families are usually not given explicitly (by listing their members) but represented implicitly. We consider the problem of efficiently computing tree representations of set families. Assuming the existence of efficient algorithms for solving the Membership and Separation problems, we prove that if a set family satisfies weak closure properties then there exists an efficient algorithm for computing a tree representation of the set family. The running time of the algorithm will mainly depend on the running times of the algorithms for the two basic problems. Our algorithm generalizes several previous results and provides a unified approach to the computation for a large class of decompositions of graphs. We also introduce a decomposition notion for directed graphs which has no undirected analogue. We show that the results of the first part of the paper are applicable to this new decomposition. Finally, we give efficient algorithms for the two basic problems and obtain an ${\cal O}(n^3)$ -time algorithm for computing a tree representation.</div></front></TEI><affiliations><list><country><li>Allemagne</li><li>Norvège</li><li>États-Unis</li></country><region><li>Rhénanie-Palatinat</li></region><settlement><li>Trèves (Allemagne)</li></settlement><orgName><li>Université de Trèves</li></orgName></list><tree><country name="Norvège"><noRegion><name sortKey="Bui Xuan, Binh Minh" sort="Bui Xuan, Binh Minh" uniqKey="Bui Xuan B" first="Binh-Minh" last="Bui-Xuan">Binh-Minh Bui-Xuan</name></noRegion><name sortKey="Bui Xuan, Binh Minh" sort="Bui Xuan, Binh Minh" uniqKey="Bui Xuan B" first="Binh-Minh" last="Bui-Xuan">Binh-Minh Bui-Xuan</name><name sortKey="Heggernes, Pinar" sort="Heggernes, Pinar" uniqKey="Heggernes P" first="Pinar" last="Heggernes">Pinar Heggernes</name><name sortKey="Heggernes, Pinar" sort="Heggernes, Pinar" uniqKey="Heggernes P" first="Pinar" last="Heggernes">Pinar Heggernes</name></country><country name="Allemagne"><region name="Rhénanie-Palatinat"><name sortKey="Meister, Daniel" sort="Meister, Daniel" uniqKey="Meister D" first="Daniel" last="Meister">Daniel Meister</name></region><name sortKey="Meister, Daniel" sort="Meister, Daniel" uniqKey="Meister D" first="Daniel" last="Meister">Daniel Meister</name></country><country name="États-Unis"><noRegion><name sortKey="Proskurowski, Andrzej" sort="Proskurowski, Andrzej" uniqKey="Proskurowski A" first="Andrzej" last="Proskurowski">Andrzej Proskurowski</name></noRegion><name sortKey="Proskurowski, Andrzej" sort="Proskurowski, Andrzej" uniqKey="Proskurowski A" first="Andrzej" last="Proskurowski">Andrzej Proskurowski</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/LNCS/Analysis
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000012 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/LNCS/Analysis/biblio.hfd -nk 000012 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= LNCS
|étape= Analysis
|type= RBID
|clé= ISTEX:E0D5AC59000A21FA35884564DF9E64538F6ECD66
|texte= A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition
}}
| This area was generated with Dilib version V0.6.31. |  |